import java.util.Arrays;
import java.util.stream.Collectors;

public class TravellingSalesmanProblem {
    public static void main(String[] args) {
        int[][] graph = {
                {0, 1, 2, 3},
                {1, 0, 6, 4},
                {2, 6, 0, 5},
                {3, 4, 5, 0},
        };
        System.out.println(tsp(graph));
        System.out.println(6 >> (0-1));
    }
    static int tsp(int[][] graph){
        int n = graph.length;
        int m = 1 << (n - 1);
        int[][] dp = new int[n][m];
        for (int i = 0; i < n; i++){
            dp[i][0] = graph[i][0];
        }
        for (int j = 1; j < m; j++){
            for (int i = 0; i < n; i++){
                dp[i][j] = Integer.MAX_VALUE / 2;
                if (contain(i, j)){
                    continue;
                }
                for (int k = 1; k < n; k++){
                    if (contain(j, k)){
                        dp[i][j] = Math.min(dp[i][j], graph[i][k] + dp[k][exclude(j ,k)]);
                    }
                }
            }
            print(dp);
        }
        return dp[0][m - 1];
    }

    static boolean contain(int set, int city){
        return (set >> (city - 1) & 1) == 1;
    }

    static int exclude(int set, int city){
        return set ^ (1 << (city - 1));
    }
    static void print(int[][] dist) {
        System.out.println("-------------------------");
        for (int[] row : dist) {
            System.out.println(Arrays.stream(row).boxed()
                    .map(x -> x >= Integer.MAX_VALUE / 2 ? "∞" : String.valueOf(x))
                    .map(s -> String.format("%2s", s))
                    .collect(Collectors.joining(",", "[", "]")));
        }
    }
}
